#ifndef __RBTREEZ_H
#define __RBTREEZ_H

#include <iostream>
#include <stack>
#include <queue>

//define DEBUG
//define DEBUG2

using namespace std;

namespace datastructureZ{

template<typename ElementType> class RBTree
{
	/**
	* 标题：参考《算法导论》实现的红黑树
	* 开始：2021-03-18:14:26
	* 完成：N/A
	* 作者：兰彦真
	*/
	
	//定义节点类型：RBTree<ElementType>::Node
	friend class Node;public:class Node
	{
		friend class RBTree<ElementType>;
		public:typedef bool ColorType;	//定义节点颜色类型
		
		/*
		定义节点颜色常量：
			RBTree<ElementType>::Node::BLACK 
			RBTree<ElementType>::Node::RED
		*/
		public:static const ColorType BLACK = false;
		public:static const ColorType RED	= true;
		//--------------------------------------------
		private:ColorType color;		//节点颜色
		
		protected:Node *lChild;			//节点左子树入口
		protected:Node *rChild;			//节点右子树入口
		protected:Node *parent;			//节点双亲
		
		protected:ElementType data;		//节点存储的数据
		//--------------------------------------------
		
		//默认构造函数
		public:Node
		(
			ColorType _color = BLACK, 
			Node* _lChild = nullptr,
			Node* _rChild = nullptr,
			Node* _parent = nullptr
		):
			color(_color),
			lChild(_lChild),	rChild(_rChild),
			parent(_parent){}
		
		//用已有数据初始化节点的构造函数
		public:Node
		(
			const ElementType& _data,
			ColorType _color = BLACK, 
			Node* _lChild = nullptr,
			Node* _rChild = nullptr,
			Node* _parent = nullptr
		):
			color(_color),
			lChild(_lChild),	rChild(_rChild),
			parent(_parent),	data(_data){}
		
		//拷贝构造函数
		public:Node(const Node& another):
			data(another.data),		color(another.color),
			lChild(another.lChild),	rChild(another.rChild),
			parent(another.parent){}
		
		public:struct StreamData
		{
			ElementType data;
			ColorType	color;
			
			StreamData(ElementType _data, ColorType	_color): data(_data), color(_color){}
		};
		
		public:StreamData getStreamData(void)
		{
			StreamData res(data, color);
			return res;
		}
	};
	
	public:template<typename itr_type> class itr:public std::iterator//迭代器抽象基类 
	<
		std::forward_iterator_tag, 
		ElementType,	Node*, 
		ElementType*,	ElementType&
	>
	{
		friend class RBTree<ElementType>;
		protected:Node* now;
		protected:Node* nil;
	
		public:itr(void):now(nullptr), nil(nullptr){}
		public:itr(const itr& another):now(another.now), nil(another.nil){}
				
		public:virtual itr_type& operator = (const itr_type& another) = 0;
		public:virtual itr_type& operator ++ (void) = 0;
		
		public:bool operator == (const itr& another) const {return now == another.now;}
		public:bool operator != (const itr& another) const {return now != another.now;}
		
		public:ElementType& operator * (void) const {return now->data;}
		public:ElementType* operator -> (void) const {return &(operator*());}
	};
	
	public:class bfs_iterator:public itr<bfs_iterator>	//层序迭代器
	{
		friend class RBTree<ElementType>;
		protected:std::queue<Node*> que;
		
		public:bfs_iterator(void):itr<bfs_iterator>(){}
		public:bfs_iterator(const bfs_iterator& another):
		itr<bfs_iterator>(another), que(another.que){}
				
		private:static void clrque(std::queue<Node*>& que)
		{
			std::queue<Node*> empty;
			swap(empty, que);
		}
					
		public:bfs_iterator& operator = (const bfs_iterator& another)
		{
			itr<bfs_iterator>::now = another.now;
			itr<bfs_iterator>::nil = another.nil;
			clrque(que);
			que = another.que;
				
			return *this;
		}
					
		public:bfs_iterator& operator ++ (void)
		{
			if(que.empty())
			{
				itr<bfs_iterator>::now = itr<bfs_iterator>::nil;
				return *this;
			}
						
			itr<bfs_iterator>::now = que.front();
			que.pop/*_front*/();
		
	
			if(itr<bfs_iterator>::now->lChild != itr<bfs_iterator>::nil) que.push/*_back*/(itr<bfs_iterator>::now->lChild);
			if(itr<bfs_iterator>::now->rChild != itr<bfs_iterator>::nil) que.push/*_back*/(itr<bfs_iterator>::now->rChild);
			
			return *this;
		}
	};
	
	public:typedef bfs_iterator iterator;
	
	public:class mid_iterator:public itr<mid_iterator>	//中序迭代器 
	{
		friend class RBTree<ElementType>;
		protected:std::stack<Node*>	stk;
		private:bool				isFirst;
		
		public:mid_iterator(void):itr<mid_iterator>(), isFirst(false){}
		public:mid_iterator(const mid_iterator& another):
			itr<mid_iterator>(another), stk(another.stk), isFirst(false)
		{if(another.isFirst) ++(*this);}
		
		private:static void clrstk(std::stack<Node*>& stk)
		{
			std::stack<Node*> empty;
			swap(empty, stk);
		}
					
		public:mid_iterator& operator = (const mid_iterator& another)
		{
			itr<mid_iterator>::now = another.now;
			itr<mid_iterator>::nil = another.nil;
			clrstk(stk);
			stk = another.stk;
			
			if(another.isFirst)
				++(*this);
			isFirst = false;
			
			return *this;
		}
		
		public:bool hasNext(void)
		{
			return stk.size() != 1  ||  itr<mid_iterator>::now->rChild != itr<mid_iterator>::nil;
		}
		
		public:mid_iterator& operator ++ (void)
		{
			if(stk.empty())
			{
				itr<mid_iterator>::now = itr<mid_iterator>::nil;
				return *this;
			}
						
			itr<mid_iterator>::now = stk.top();
			
			while(itr<mid_iterator>::now != itr<mid_iterator>::nil)
			{
				stk.push(itr<mid_iterator>::now->lChild);
				itr<mid_iterator>::now = itr<mid_iterator>::now->lChild;
			}
			
			stk.pop();
				
			if(stk.empty())
			{
				itr<mid_iterator>::now = itr<mid_iterator>::nil;
				return *this;
			}
			
			itr<mid_iterator>::now = stk.top();
			stk.pop();
			stk.push(itr<mid_iterator>::now->rChild);
			
			return *this;
		}
	};
	//--------------------------------------------
	protected:Node *const NIL;			//哨兵节点（每棵红黑树都有一个自己的哨兵节点）
	protected:Node *root;				//树根节点
	protected:iterator op, ed;			//层序遍历迭代器的起点和终点
	protected:mid_iterator mop, med;	//中序遍历迭代器的起点和终点
	//--------------------------------------------
	
	public:iterator begin(void)			const {return op;}
	public:iterator end(void)			const {return ed;}
	public:mid_iterator mid_begin(void)	const {return mop;}			
	public:mid_iterator mid_end(void)	const {return med;}
	
	public:RBTree(void):NIL(new Node(Node::BLACK)), root(NIL)
	{
		//设定哨兵节点
		NIL->lChild = NIL->rChild = NIL->parent = NIL;
		
		//设定迭代器
		mop.now = op.now = root;
		mop.nil = op.nil = NIL;
		
		mop.stk.push(root);
		if(root->lChild != NIL)
			op.que.push(root->lChild);
		if(root->rChild != NIL)
			op.que.push(root->rChild);
		med.now = ed.now = NIL;
		
		mop.isFirst = true;
	}	~RBTree(void) {delete NIL;}
	
	private:void lRotate(Node *nowAt)			//节点左旋转
	{
		Node *nowParent = nowAt->parent;
		Node *nowRChild = nowAt->rChild;		//01 y = x.right
		
		nowAt->rChild = nowRChild->lChild;		//02 x.right = y.left
		
		if(nowRChild->lChild != NIL)			//03 if y.left != T.nil
			nowRChild->lChild->parent = nowAt;	//04	y.left.p = x
		
		nowRChild->parent = nowParent;			//05 y.p = x.p
		
		if(nowParent == NIL)					//06 if x.p == T.nil
			root = nowRChild;					//07 	T.root = y
		else if(nowAt == nowParent->lChild)		//08 if x == x.p.left
			nowParent->lChild = nowRChild;		//09 	x.p.left = y
		else nowParent->rChild = nowRChild;		//10 else x.p.right = y
		
		nowRChild->lChild = nowAt;				//11 y.left = x
		nowAt->parent = nowRChild;				//12 x.p = y
	}
	
	private:void rRotate(Node *nowAt)			//节点右旋转
	{
		Node *nowParent = nowAt->parent;
		Node *nowLChild = nowAt->lChild;		//01 y = x.left
		
		nowAt->lChild = nowLChild->rChild;		//02 x.left = y.right
		
		if(nowLChild->rChild != NIL)			//03 if y.right != T.nil
			nowLChild->rChild->parent = nowAt;	//04	y.right.p = x
		
		nowLChild->parent = nowParent;			//05 y.p = x.p
		
		if(nowParent == NIL)					//06 if x.p == T.nil
			root = nowLChild;					//07 	T.root = y
		else if(nowAt == nowParent->rChild)		//08 if x == x.p.right
			nowParent->rChild = nowLChild;		//09 	x.p.right = y
		else nowParent->lChild = nowLChild;		//10 else x.p.left = y
		
		nowLChild->rChild = nowAt;				//11 y.right = x
		nowAt->parent = nowLChild;				//12 x.p = y
	}
	
	private:void insertFix(Node *nowAt) //插入平衡修复过程
	{
		Node *nowParent = NIL;
		Node *uncle = NIL;
		while((nowParent = nowAt->parent)->color == Node::RED)
		{
			if(nowParent == nowParent->parent->lChild)
			{//当插入点的双亲节点是左节点
				uncle = nowParent->parent->rChild;
				
				if(uncle->color == Node::RED)
				{//情况1，将其双亲节点与双亲的双亲节点颜色翻转（此时双亲的双亲节点肯定为黑色，否则不满足性质4）
					nowParent->color = uncle->color = Node::BLACK;
					nowParent->parent->color = Node::RED;
					nowAt = nowParent->parent;
				}
				else
				{//情况2、3
					if(nowAt == nowParent->rChild)
					{//情况2
						nowAt = nowParent;
						lRotate(nowAt);
					}
					else
					{//情况3
						nowParent->color = Node::BLACK;
						nowParent->parent->color = Node::RED;
						rRotate(nowParent->parent);
					}
				}
			}
			else
			{//当插入点的双亲节点是右节点
				uncle = nowParent->parent->lChild;
				
				if(uncle->color == Node::RED)
				{//情况1，将其双亲节点与双亲的双亲节点颜色翻转（此时双亲的双亲节点肯定为黑色，否则不满足性质4）
					nowParent->color = uncle->color = Node::BLACK;
					nowParent->parent->color = Node::RED;
					nowAt = nowParent->parent;
				}
				else
				{//情况2、3
					if(nowAt == nowParent->lChild)
					{//情况2
						nowAt = nowParent;
						rRotate(nowAt);
					}
					else
					{//情况3
						nowParent->color = Node::BLACK;
						nowParent->parent->color = Node::RED;
						lRotate(nowParent->parent);
					}
				}
			}
		}
		root->color = Node::BLACK;
	}
	
	public:ElementType* _insert(const ElementType& _data) //插入成功返回nullptr，插入元素已存在返回该元素的地址
	{
		Node *parentNode = NIL; //插入点的双亲
		Node *nowAt = root;		//遍历指针
		
		while(nowAt != NIL)		//自顶向下寻找插入点
		{
			parentNode = nowAt;
			if(nowAt->data < _data)			nowAt = nowAt->rChild;
			else if(nowAt->data > _data)	nowAt = nowAt->lChild;
			else							return &nowAt->data;
		}
		
		Node *newNode = new Node(_data, Node::RED, NIL, NIL, parentNode);
		
		if(parentNode == NIL) root = newNode; //树空，插入节点作为新根
		else if(_data < parentNode->data) parentNode->lChild = newNode;
		else							  parentNode->rChild = newNode;
		
		insertFix(newNode);		//修复平衡
		
		//重置迭代器
		mop.now = op.now = root;
		iterator::clrque(op.que);
		mid_iterator::clrstk(mop.stk);
		
		mop.stk.push(root);
		if(root->lChild != NIL)
			op.que.push(root->lChild);
		if(root->rChild != NIL)
			op.que.push(root->rChild);
		
		return nullptr;
	}
	
	public:bool insert(const ElementType& _data)
	{
		return _insert(_data) == nullptr;
	}
	
	public:RBTree& operator << (const ElementType& _data)
	{
		_insert(_data);
		return *this;
	}
	
	protected:Node* getMaxNode(Node* nowAt)
	{
		if(nowAt == nullptr) return nullptr;
		
		while(nowAt->rChild != NIL)
			nowAt = nowAt->rChild;
			
		return nowAt;
	}
	
	protected:const Node* getMaxNode(const Node* nowAt) const
	{
		if(nowAt == nullptr) return nullptr;
		
		while(nowAt->rChild != NIL)
			nowAt = nowAt->rChild;
			
		return nowAt;
	}
	
	protected:Node* getMinNode(Node* nowAt)
	{
		if(nowAt == nullptr) return nullptr;
		
		while(nowAt->lChild != NIL)
			nowAt = nowAt->lChild;
			
		return nowAt;
	}
	
	protected:const Node* getMinNode(const Node* nowAt) const
	{
		if(nowAt == nullptr) return nullptr;
		
		while(nowAt->lChild != NIL)
			nowAt = nowAt->lChild;
			
		return nowAt;
	}
	
	protected:Node* searchNode(const ElementType& _data)
	{
		Node *nowAt = root;		//遍历指针
		while(nowAt != NIL)		//自顶向下寻找目标节点
		{
			if(nowAt->data < _data)			nowAt = nowAt->rChild;
			else if(nowAt->data > _data)	nowAt = nowAt->lChild;
			else break;
		}
		
		return nowAt;
	}
	
	private:template<typename T> static void _swap(T& a, T& b)
	{
		T t = a;
		a = b;
		b = t;
	}
	
	private:void removeFix(Node* nowAt)
	{
		Node* brother = NIL;
		while(nowAt != root  &&  nowAt->color == Node::BLACK)
		{
			if(nowAt == nowAt->parent->lChild)
			{
				brother = nowAt->parent->rChild;
				
				if(brother->color == Node::RED)	//case 1
				{
					//cout<<"testing case 1"<<endl;
					_swap(nowAt->parent->color, brother->color);
					lRotate(nowAt->parent);
					brother = nowAt->parent->rChild;
				}
				
				if								//case 2
				(
					brother->lChild->color == Node::BLACK &&
					brother->rChild->color == Node::BLACK
				)
				{
					//cout<<"testing case 2"<<endl;
					brother->color = Node::RED;
					nowAt = nowAt->parent;
				}							//case 3
				else 
				{
					if(brother->rChild->color == Node::BLACK)
					{
						//cout<<"testing case 3"<<endl;
						brother->color = Node::RED;
						brother->lChild->color = Node::BLACK;
						rRotate(brother);
						brother = nowAt->parent->rChild;
					}							//case 4
					//cout<<"testing case 4"<<endl;
					brother->color = nowAt->parent->color;
					nowAt->parent->color = Node::BLACK;
					brother->rChild->color = Node::BLACK;
					lRotate(nowAt->parent);
					
					nowAt = root;
				}
			}
			else
			{
				brother = nowAt->parent->lChild;
				
				if(brother->color == Node::RED)	//case 1
				{
					//cout<<"testing case 1"<<endl;
					_swap(nowAt->parent->color, brother->color);
					rRotate(nowAt->parent);
					brother = nowAt->parent->lChild;
				}
				
				if								//case 2
				(
					brother->rChild->color == Node::BLACK &&
					brother->lChild->color == Node::BLACK
				)
				{
					//cout<<"testing case 2"<<endl;
					brother->color = Node::RED;
					nowAt = nowAt->parent;
				}								//case 3
				else 
				{
					if(brother->lChild->color == Node::BLACK)
					{
						//cout<<"testing case 3"<<endl;
						brother->color = Node::RED;
						brother->rChild->color = Node::BLACK;
						lRotate(brother);
						brother = nowAt->parent->lChild;
					}							//case 4
					//cout<<"testing case 4"<<endl;
					brother->color = nowAt->parent->color;
					nowAt->parent->color = Node::BLACK;
					brother->lChild->color = Node::BLACK;
					rRotate(nowAt->parent);
					
					nowAt = root;
				}
			}
		}
		
		nowAt->color = Node::BLACK;
	}
	
	private:Node* _remove(Node* target)
	{
		if(target == NIL) return nullptr;
		#ifdef DEBUG2
			cout<<"OK1"<<endl;
		#endif
		typename Node::ColorType targetColor = target->color;
		Node* removedPosition = NIL;
		Node* tempParent = target->parent;
		
		if(target->rChild == NIL)
		{
			#ifdef DEBUG2
				cout<<"Case L"<<endl;
			#endif
			removedPosition = target->lChild;
			//removedPosition->parent = target; //即便是NIL
			
			if(target == tempParent->lChild)
				tempParent->lChild = removedPosition;
			else tempParent->rChild = removedPosition;
			
			removedPosition->parent = tempParent;
			if(target == root) root = NIL;
			//removedPosition->color = targetColor;
		}
		else if(target->lChild == NIL)
		{
			#ifdef DEBUG2
				cout<<"Case R"<<endl;
			#endif
			case_2:
			removedPosition = target->rChild;
			//removedPosition->parent = target; //即便是NIL
			
			if(target == tempParent->lChild)
				tempParent->lChild = removedPosition;
			else tempParent->rChild = removedPosition;
			
			removedPosition->parent = tempParent;
			if(target == root) root = NIL;
			//removedPosition->color = targetColor;
		}
		else
		{
			#ifdef DEBUG2
				cout<<"Case Double"<<endl;
			#endif
			removedPosition = getMinNode(target->rChild);
			tempParent = removedPosition->parent;
			
			_swap(target->data, removedPosition->data);
			
			target = removedPosition;
			targetColor = target->color;
			tempParent = target->parent;
			goto case_2;
		}
		#ifdef DEBUG2
			cout<<"OK2"<<endl;
		#endif
		if(targetColor == Node::BLACK) removeFix(removedPosition);
		//cout<<endl<<"x:"<<removedPosition->data<<endl;
		#ifdef DEBUG2
			cout<<"OK3"<<endl;
		#endif
		return target;
	}
	
	public:bool remove(const ElementType& _data)
	{
		Node* target = _remove(searchNode(_data));
		if(target == nullptr) return false;
		else
		{
			delete(target);
			return true;
		}
	}
	
	public:const ElementType* search(const ElementType& _data)
	{
		Node* target = searchNode(_data);
		if(target != NIL) return &(target->data);
		else return nullptr;
	}
	
	private:void insertWithoutEnbalance(const typename Node::StreamData& _data) //
	{
		Node *parentNode = NIL; //插入点的双亲
		Node *nowAt = root;		//遍历指针
		
		while(nowAt != NIL)		//自顶向下寻找插入点
		{
			parentNode = nowAt;
			if(nowAt->data < _data.data)		nowAt = nowAt->rChild;
			else if(nowAt->data > _data.data)	nowAt = nowAt->lChild;
			else return;
		}
		
		Node *newNode = new Node(_data.data, _data.color, NIL, NIL, parentNode);
		
		if(parentNode == NIL) root = newNode; //树空，插入节点作为新根
		else if(_data.data < parentNode->data)	parentNode->lChild = newNode;
		else									parentNode->rChild = newNode;
		
		//insertFix(newNode);	//修复平衡
		
		//重置迭代器
		mop.now = op.now = root;
		iterator::clrque(op.que);
		mid_iterator::clrstk(mop.stk);
		
		mop.stk.push(root);
		if(root->lChild != NIL)
			op.que.push(root->lChild);
		if(root->rChild != NIL)
			op.que.push(root->rChild);
	}
	
	#ifdef DEBUG
	private:static void _testPriShow(RBTree<ElementType>* tree, Node* nowAt)
	{
		if(nowAt != tree->NIL)
		{
			cout<<nowAt->data<<':'<<(nowAt->color?'R':'B')<<' ';
			_testPriShow(tree, nowAt->lChild);
			_testPriShow(tree, nowAt->rChild);
		}
	}
	
	public:void testShow(void)
	{
		_testPriShow(this, root);
	}
	#endif
};

};
#endif